package chapter_01;

/*
 * 一、综述
 * 		1. 数据结构的概述
 * 		数据结构				优点										缺点
 * 		数组					插入快，如果知道下标，可以非常快地存取		查找慢，删除慢，大小固定
 * 		有序数组				比无序数组查找快							删除和插入慢，大小固定
 * 		栈					提供后进先出方式的存取					    存取其他项很慢
 * 		队列					提供先进先出方式的存取					    存取其他项很慢
 * 		链表					插入快，删除快							查找慢
 * 		二叉树				查找、插入、删除都快（如果树保持平衡）		删除算法复杂
 * 		红-黑树				查找、插入、删除都快。树总是平衡的			算法复杂
 * 		2-3-4树				查找、插入、删除都快。树总是平衡的			算法复杂
 * 		哈希表				如果关键字已知则存取极快，插入快			删除慢，如果不知道
 * 																	关键字则存取很慢，对存储
 * 																	空间使用不充分
 * 		堆					插入、删除快，对最大数据项的存取很快		    对其他数据项存取慢
 * 		图					对现实世界建模							有些算法慢且复杂
 * 
 * 		2. 算法的概述
 * 		大多数数据结构都需要知道如何：
 * 		• 插入一套新的数据项
 * 		• 寻找某一特定的数据项
 * 		• 删除某一特定的数据项
 * 
 * 		3. Java数据结构的类库
 * 		Java.util包含有诸如向量（一个可扩充的数组）、栈、库（dictionary）和哈希表等数据
 * 		类型的数据结构。
 */

// 大话数据结构
/*
一、绪论
	1. 逻辑结构
	A. 集合结构
	集合结构：集合结构中的数据元素除了同属一个集合外，它们之间没有其他关系。
	线性结构：线性结构中的数据元素之间是一对一的关系。
	树形结构：树形结构中的元素存在一种一对多的层次关系。
	图形结构：图形结构的数据元素是多对多的关系。

	B. 物理结构（存储结构）
	物理结构：是指数据的逻辑的逻辑结构在计算机中的存储形式。
	数据元素的存储结构形式有两种：顺序存储和链式存储。
	顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
	链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

	2. 抽象数据类型
	数据类型：指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
	抽象数据类型（ADT）：指一个数学模型及其定义在该模型上的一组操作。


二、算法
	1. 两种算法的比较
	from _functools import reduce
	a = range(101)
	print(reduce(lambda x, y: x + y, a))

	n = 100
	sum_ = (1 + n) * n /2
	print(sum_)

	2. 算法定义
	算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个
	操作。

	3. 算法的特性
	算法具有五个特性：输入、输出、有穷性、确定性和可行性。
		A. 算法具有零个或多个输入。
		算法至少有一个或多个输出，算法是一定需要输出的，不需要输出，用这个算法干嘛？

		B. 有穷性
		算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间内完
		成。

		C. 确定性
		算法的每一步骤都具有特定的含义，不会出现二义性。

		D. 可行性
		算法的每一步都是可行的，也就是说，每一步都能通过执行有限次数完成。

	4. 算法设计的要求
		A. 正确性
		算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能挣钱反映问题的需求、能够
		得到问题的正确答案。

		B. 可读性
		算法设计的另一目的是便于阅读、理解和交流。

		C. 健壮性
		当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

		D. 时间效率高和存储率低
		设计算法应该尽量满足时间效率高和存储量低的需求。

	5. 算法效率的度量方法
		A. 事后统计方法（不推荐）
		这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间
		进行比较，从而确定算法效率的高低。

		B. 事前分析估算方法
		在计算机程序编制前，依据统计方法对算法进行估算。

	6. 函数的渐进增长
	输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐
	进增长的。
	函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比
	g(n)大，那么，我们说f(n)的增长渐进快与g(n)。
	对于函数的渐进增长，下面有几点是值得关注的问题：
		A. 常数
		对于算法复杂度为2n+3和复杂度为3n+1的算法，常数是可以忽略掉的。
		B. 乘数
		对于算法复杂度为4n+8和复杂度为2n^2+1的算法，与最高次方项相乘的常数并不重要。
		C. 最高项的指数
		最高项指数大的，函数随着n的增长，结果也会变得增长特别快。
		判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）
		的阶数。
		D. 算法的增长
		某个算法，随着n的增大，他会越来越优于另一算法，或者越来越差于另一算法。

	7. 时间复杂度
		A. 定义
		在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并
		确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问
		题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为
		时间复杂度。其中f(n)的问题规模n的某个函数。
		这样用大写O()来体现算法时间复杂度的记法，我们称为大O记法。
		一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

		B. 推导大O阶方法
		a. 用常数1取代运行时间中的所有加法常数。
		b. 在修改后的运行次数函数中，只保留最高阶项。
		c. 如果最高阶存在且不是1，则除去与这个项相乘的常数。
		得到的结果就是大O阶。

		C. 常数阶
		O(1)。

		D. 线性阶
		O(n)。

		E. 对数阶
		int count = 1;
		while (count < n)
			count = count * 2;
		由于每次count2乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循
		环。由2^x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。

		F. 平方阶
		基本的两层嵌套循环的时间复杂度就是O(n^2)。
		对于下面这个循环：
		int i, j;
		for (i = 0; i < n; i++){
			for (j = i; j < n; j++) {
				//时间复杂度为O(1)的程序步骤序列
			}
		}
		由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次，当i=n-1时，执行了1次。所以总的执行次
		数为：
		n+(n-1)+(n-2)+...+1=n(n+1)/2=n^2/2+n/2
		我们使用推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留
		n2/2；第三条，去除这个项相乘的常数，也就是去除1/2，最终这段代码的时间复杂度为O(n^2)。
		大O阶推导难的是对数列的一些相关运算，这更多的是考察我们的数学知识和能力。

	8. 常见的时间复杂度
	执行次数函数			阶		非正式术语
	12						O(1)	常数阶
	2n+3					O(n)	线性阶
	3n^2+2n+1				O(n^2)	平方阶
	5log2n+20				O(logn)	对数阶
	2n+3nlog2n+19			O(nlogn)	nlogn阶
	6n^3+2n^2+3n+4			O(n^3)		立方阶
	2^n						O(2n)		指数阶
	常用的时间复杂度所耗费的时间从小到大依次是：
	O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
	n^3及其后面的复杂度都十分不现实，都是噩梦般的运行时间。

	9. 最坏情况与平均情况
	最坏情况运行时间是一种保障，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通
	常，除非特别指定，我们提到的运行时间都是最坏的情况的运行时间。
	平均时间是所有情况中最优意义的，因为它是期望的运行时间。
	对于所有算法，在没有特殊说明下，对它们的时间复杂度度量都是指最坏时间复杂度。

	10. 算法空间复杂度
	算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，
	其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。
	一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还
	需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只要分析
	该算法实现时所需的辅助单元即可。若算法执行时所需的空间相对于输入数据量而言是个常数，则称此
	算法为原地工作，空间复杂度为O(1)。
 */


public class chapter_01 {

}
